﻿/** 
 * Copyright (c) 2001 University of Maryland, College Park, MD 20742, USA
 * Copyright (c) 2005 In4Arch
 *
 *  The MIT License
 *  Permission is hereby granted, free of charge, to any person obtaining a copy of this 
 *  software and associated documentation files (the "Software"), to deal in the Software 
 *  without restriction, including without limitation the rights to use, copy, modify, merge, 
 *  publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons 
 *  to whom the Software is furnished to do so, subject to the following conditions:
 *
 *  The above copyright notice and this permission notice shall be included in all copies 
 *  or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
 *  INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A 
 *  PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 
 *  HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF 
 *  CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE 
 *  OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 * Authors: Benjamin B. Bederson and Martin Wattenberg 2001 
 * http://www.cs.umd.edu/hcil/treemap-history/index.shtml
 * 
 * Author: moedusa moedusa@gmail.com 2005
 * http://moedusa.name/
 *
 * Author: Nikita Shlyakhov shlyakhov@mail.ru 2006
 **/


import in4arch.alg.treemap.MapLayout; 
import in4arch.alg.treemap.MapModel; 
import in4arch.alg.treemap.Rect; 

class in4arch.alg.treemap.OrderedTreemap implements MapLayout {
	
    static public var PIVOT_BY_MIDDLE:Number = 1;
    static public var PIVOT_BY_SPLIT_SIZE:Number = 2;
    static public var PIVOT_BY_BIGGEST:Number = 3;

    private var items_array:Array;
	private var result_rects_array:Array;
    private var layoutBox:Rect;
    private var pivotType:Number = PIVOT_BY_MIDDLE;

    public function getName():String {
	  return "OrderedTreemap";
    }

    public function getDescription():String {
	  return "An Ordered Squarified Treemap";
    }

    public function setPivotType(pivotType:Number):Void {
	  this.pivotType = pivotType;
    }
    
    public function layout(model:MapModel, bounds:Rect):Void {
		
        var r:Rect = new Rect(0, 0, bounds.w, bounds.h);
        layoutAtOrigin(model, r);
        var m_array:Array = model.getItems();
		
        for (var i=0; i < m_array.length; i++) {
            m_array[i].getRect().x+=bounds.x;
            m_array[i].getRect().y+=bounds.y;
        }
		
    }

    public function layoutAtOrigin(model:MapModel, bounds:Rect):Void {
		
	  items_array = model.getItems();
	  layoutBox = bounds;

		var totalSize:Number = 0;
		var area:Number = layoutBox.w * layoutBox.h;
	
		for (var i=0; i<items_array.length; i++) {
			totalSize += items_array[i].getSize();
		}
	
		var scaleFactor:Number = Math.sqrt(area / totalSize);
		var box:Rect = new Rect(layoutBox.x, layoutBox.y, layoutBox.w, layoutBox.h);
		box.x /= scaleFactor;
		box.y /= scaleFactor;
		box.w /= scaleFactor;
		box.h /= scaleFactor;
	
		var sizes_array:Array = new Array(items_array.length);
		for (var i=0; i<items_array.length; i++) {
			sizes_array[i] = items_array[i].getSize();
		}
		
		var results_array:Array = orderedLayoutRecurse(sizes_array, box);
		
		var rect:Rect;
		for (var i=0; i<items_array.length; i++) {
			rect = items_array[i].getRect();
			rect.x = results_array[i].x * scaleFactor;
			rect.y = results_array[i].y * scaleFactor;
			rect.w = results_array[i].w * scaleFactor;
			rect.h = results_array[i].h * scaleFactor;
	
			rect.x += bounds.x;
			rect.y += bounds.y;
			items_array[i].setRect(rect);
		}
    }

    private function orderedLayoutRecurse(sizes_array:Array, box:Rect):Array {

		var l1:Array = null;
		var l2:Array = null;
		var l3:Array = null;
		var l1Size:Number = 0;
		var l2Size:Number = 0;
		var l3Size:Number = 0;
		var r1:Rect = null;
		var r2:Rect = null;
		var r3:Rect = null;
		var rp:Rect = null;
		var r1AR:Number;
		var pivotIndex:Number = computePivotIndex(sizes_array);
		var pivotSize:Number = sizes_array[pivotIndex];
		var pivotAR:Number;
		var boxes:Array = null;
		var boxAR:Number;
		var box2:Rect;
		var box2AR:Number;
		var d:Number;
		var w:Number, h:Number;
		var ratio:Number;
		
        // Stopping condition
		boxAR = box.w / box.h;
		d = sizes_array.length - pivotIndex - 1;
	
		if (sizes_array.length == 1) {
			boxes = new Array(1);
			boxes[0] = box;
			return boxes;
		}
	
		if (sizes_array.length == 2) {
			boxes = new Array(2);
			ratio = sizes_array[0] / (sizes_array[0] + sizes_array[1]);
			if (boxAR >= 1) {
				w = ratio * box.w;
				boxes[0] = new Rect(box.x, box.y, w, box.h);
				boxes[1] = new Rect(box.x + w, box.y, box.w - w, box.h);
			} else {
				h = ratio * box.h;
				boxes[0] = new Rect(box.x, box.y, box.w, h);
				boxes[1] = new Rect(box.x, box.y + h, box.w, box.h - h);
			}
			return boxes;
		}
	
		// First, compute R1
		l1 = new Array(pivotIndex);
		arraycopy(sizes_array, 0, l1, 0, pivotIndex);
		l1Size = computeSize(l1);
		if (boxAR >= 1) {
			h = box.h;
			w = l1Size / h;
			r1 = new Rect(box.x, box.y, w, h);
			box2 = new Rect(r1.x + r1.w, box.y, box.w - r1.w, box.h);
		} else {
			w = box.w;
			h = l1Size / w;
			r1 = new Rect(box.x, box.y, w, h);
			box2 = new Rect(r1.x, r1.y + r1.h, box.w, box.h - r1.h);
		}
	
		// Then compute R2 and R3
		box2AR = box2.w / box2.h;
		if (d >= 3) {
			// First, split up l2 and l3
			var _first:Boolean = true;
			var bestAR:Number = 0;
			var bestW:Number = 0;
			var bestH:Number = 0;
			var bestIndex:Number = 0;
			for (var i=pivotIndex+1; i<sizes_array.length; i++) {
				l2Size = computeSize2(sizes_array, pivotIndex+1, i);
				l3Size = computeSize2(sizes_array, i+1, sizes_array.length-1);
				ratio = (pivotSize + l2Size) / (pivotSize + l2Size + l3Size);
				if (boxAR >= 1) {
					w = ratio * box2.w;
					ratio = pivotSize / (pivotSize + l2Size);
					h = ratio * box2.h;
				} else {
					h = ratio * box2.h;
					ratio = pivotSize / (pivotSize + l2Size);
					w = ratio * box2.w;
				}
				pivotAR = w / h;
				if (_first) {
					_first = false;
					bestAR = pivotAR;
					bestW = w;
					bestH = h;
					bestIndex = i;
				} else if (Math.abs(pivotAR - 1) < Math.abs(bestAR - 1)) {
					bestAR = pivotAR;
					bestW = w;
					bestH = h;
					bestIndex = i;
				}		    
			}
			l2 = new Array(bestIndex - pivotIndex);
			arraycopy(sizes_array, pivotIndex+1, l2, 0, l2.length);
			if ((sizes_array.length-1-bestIndex) > 0) {
				l3 = new Array(sizes_array.length-1 - bestIndex);
				arraycopy(sizes_array, bestIndex+1, l3, 0, l3.length);
			} else {
				l3 = null;
			}
			if (boxAR >= 1) {
				rp = new Rect(box2.x, box2.y, bestW, bestH);
				r2 = new Rect(box2.x, box2.y + bestH, bestW, box2.h - bestH);
			if (l3 != null) {
				r3 = new Rect(box2.x + bestW, box2.y, box2.w - bestW, box2.h);
			}
			} else {
			rp = new Rect(box2.x, box2.y, bestW, bestH);
			r2 = new Rect(box2.x + bestW, box2.y, box2.w - bestW, bestH);
			if (l3 != null) {
				r3 = new Rect(box2.x, box2.y + bestH, box2.w, box2.h - bestH);
			}
			}
		} else if (d > 0) {
					// l3 is null
			l2 = new Array(d);
			arraycopy(sizes_array, pivotIndex+1, l2, 0, d);
			ratio = pivotSize / (pivotSize + computeSize(l2));
			if (boxAR >= 1) {
			h = ratio * box2.h;
			rp = new Rect(box2.x, box2.y, box2.w, h);
			r2 = new Rect(box2.x, box2.y + h, box2.w, box2.h - h);
			} else {
			w = ratio * box2.w;
			rp = new Rect(box2.x, box2.y, w, box2.h);
			r2 = new Rect(box2.x+ w, box2.y, box2.w - w, box2.h);
			}
		} else {
			rp = box2;
		}
	
		// Finally, recurse on sublists
		var l1boxes:Array = null;
		var l2boxes:Array = null;
		var l3boxes:Array = null;
		var numBoxes:Number = 0;
	
		if (l1.length > 1) {
			l1boxes = orderedLayoutRecurse(l1, r1);
		} else if (l1.length == 1) {
			l1boxes = new Array(1);
			l1boxes[0] = r1;
		}
	
		if (l2 != null) {
			if (l2.length > 1) {
				l2boxes = orderedLayoutRecurse(l2, r2);
			} else if (l2.length == 1) {
				l2boxes = new Array(1);
				l2boxes[0] = r2;
			}
		}
	
		if (l3 != null) {
			if (l3.length > 1) {
				l3boxes = orderedLayoutRecurse(l3, r3);
			} else if (l3.length == 1) {
				l3boxes = new Array(1);
				l3boxes[0] = r3;
			}
		}
	
		numBoxes = l1.length + 1;
		if (l2 != null) {
			numBoxes += l2.length;
		}
		
		if (l3 != null) {
			numBoxes += l3.length;
		}
		
		boxes = new Array(numBoxes);
		var i:Number = 0;
		if (l1boxes != null) {
			arraycopy(l1boxes, 0, boxes, 0, l1boxes.length);
			i = l1boxes.length;
		}
		boxes[i] = rp;
		i++;
		if (l2 != null) {
			arraycopy(l2boxes, 0, boxes, i, l2boxes.length);
		}
		if (l3 != null) {
			i += l2boxes.length;
			arraycopy(l3boxes, 0, boxes, i, l3boxes.length);
		}
	
		boxes = tryAlternativeLayouts(sizes_array, box, boxes);
		return boxes;
    }

    private function tryAlternativeLayouts(sizes:Array, box:Rect, layoutBoxes:Array):Array {
		var boxes:Array = layoutBoxes;
		var nboxes:Array = null;
		var ratio1:Number, ratio2:Number, ratio3:Number, ratio4:Number, ratio5:Number;
		var w:Number, h:Number;
		var w1:Number, w2:Number, w3:Number, w4:Number, w5:Number;
		var h1:Number, h2:Number, h3:Number, h4:Number, h5:Number;
		var boxAR:Number = box.w / box.h;
		var origAvgAR:Number;
		var newAvgAR:Number;
	
		if (sizes.length == 3) {
			// Try snake alg.
			nboxes = new Array(3);
			ratio1 = (sizes[0]) / (sizes[0] + sizes[1] + sizes[2]);
			ratio2 = (sizes[1]) / (sizes[0] + sizes[1] + sizes[2]);
			ratio3 = (sizes[2]) / (sizes[0] + sizes[1] + sizes[2]);
			if (boxAR >= 1) {
				h = box.h;
				w1 = ratio1 * box.w;
				w2 = ratio2 * box.w;
				w3 = ratio3 * box.w;
				nboxes[0] = new Rect(box.x, box.y, w1, h);
				nboxes[1] = new Rect(box.x + w1, box.y, w2, h);
				nboxes[2] = new Rect(box.x + w1 + w2, box.y, w3, h);
			} else {
				w = box.w;
				h1 = ratio1 * box.h;
				h2 = ratio2 * box.h;
				h3 = ratio3 * box.h;
				nboxes[0] = new Rect(box.x, box.y, w, h1);
				nboxes[1] = new Rect(box.x, box.y + h1, w, h2);
				nboxes[2] = new Rect(box.x, box.y + h1 + h2, w, h3);
			}
	
			origAvgAR = computeAverageAspectRatio(boxes);
			newAvgAR = computeAverageAspectRatio(nboxes);
			
			if (newAvgAR < origAvgAR) {
				boxes = nboxes;
			}
		}
	
		if (sizes.length == 4) {
			// Try quad alg.
			nboxes = new Array(4);
			ratio1 = (sizes[0] + sizes[1]) / (sizes[0] + sizes[1] + sizes[2] + sizes[3]);
			if (boxAR >= 1) {
				w = ratio1 * box.w;
				ratio2 = (sizes[0]) / (sizes[0] + sizes[1]);
				h = ratio2 * box.h;
				nboxes[0] = new Rect(box.x, box.y, w, h);
				nboxes[1] = new Rect(box.x, box.y + h, w, box.h - h);
				ratio2 = (sizes[2]) / (sizes[2] + sizes[3]);
				h = ratio2 * box.h;
				nboxes[2] = new Rect(box.x + w, box.y, box.w - w, h);
				nboxes[3] = new Rect(box.x + w, box.y + h, box.w - w, box.h - h);
			} else {
				h = ratio1 * box.h;
				ratio2 = (sizes[0]) / (sizes[0] + sizes[1]);
				w = ratio2 * box.w;
				nboxes[0] = new Rect(box.x, box.y, w, h);
				nboxes[1] = new Rect(box.x, box.y + h, w, box.h - h);
				ratio2 = (sizes[2]) / (sizes[2] + sizes[3]);
				h = ratio2 * box.h;
				nboxes[2] = new Rect(box.x + w, box.y, box.w - w, h);
				nboxes[3] = new Rect(box.x + w, box.y + h, box.w - w, box.h - h);
			}
	
			origAvgAR = computeAverageAspectRatio(boxes);
			newAvgAR = computeAverageAspectRatio(nboxes);
			if (newAvgAR < origAvgAR) {
				boxes = nboxes;
			}
	
			// Then try 4 snake alg.
			nboxes = new Array(4);
			ratio1 = (sizes[0]) / (sizes[0] + sizes[1] + sizes[2] + sizes[3]);
			ratio2 = (sizes[1]) / (sizes[0] + sizes[1] + sizes[2] + sizes[3]);
			ratio3 = (sizes[2]) / (sizes[0] + sizes[1] + sizes[2] + sizes[3]);
			ratio4 = (sizes[3]) / (sizes[0] + sizes[1] + sizes[2] + sizes[3]);
			if (boxAR >= 1) {
				h = box.h;
				w1 = ratio1 * box.w;
				w2 = ratio2 * box.w;
				w3 = ratio3 * box.w;
				w4 = ratio4 * box.w;
				nboxes[0] = new Rect(box.x, box.y, w1, h);
				nboxes[1] = new Rect(box.x + w1, box.y, w2, h);
				nboxes[2] = new Rect(box.x + w1 + w2, box.y, w3, h);
				nboxes[3] = new Rect(box.x + w1 + w2 + w3, box.y, w4, h);
			} else {
				w = box.w;
				h1 = ratio1 * box.h;
				h2 = ratio2 * box.h;
				h3 = ratio3 * box.h;
				h4 = ratio4 * box.h;
				nboxes[0] = new Rect(box.x, box.y, w, h1);
				nboxes[1] = new Rect(box.x, box.y + h1, w, h2);
				nboxes[2] = new Rect(box.x, box.y + h1 + h2, w, h3);
				nboxes[3] = new Rect(box.x, box.y + h1 + h2 + h3, w, h4);
			}
	
			origAvgAR = computeAverageAspectRatio(boxes);
			newAvgAR = computeAverageAspectRatio(nboxes);
			if (newAvgAR < origAvgAR) {
				boxes = nboxes;
			}
		}
	
		if (sizes.length == 5) {
			// Try 5 snake alg.
			nboxes = new Array(5);
			ratio1 = (sizes[0]) / (sizes[0] + sizes[1] + sizes[2] + sizes[3] + sizes[4]);
			ratio2 = (sizes[1]) / (sizes[0] + sizes[1] + sizes[2] + sizes[3] + sizes[4]);
			ratio3 = (sizes[2]) / (sizes[0] + sizes[1] + sizes[2] + sizes[3] + sizes[4]);
			ratio4 = (sizes[3]) / (sizes[0] + sizes[1] + sizes[2] + sizes[3] + sizes[4]);
			ratio5 = (sizes[4]) / (sizes[0] + sizes[1] + sizes[2] + sizes[3] + sizes[4]);
			if (boxAR >= 1) {
				h = box.h;
				w1 = ratio1 * box.w;
				w2 = ratio2 * box.w;
				w3 = ratio3 * box.w;
				w4 = ratio4 * box.w;
				w5 = ratio5 * box.w;
				nboxes[0] = new Rect(box.x, box.y, w1, h);
				nboxes[1] = new Rect(box.x + w1, box.y, w2, h);
				nboxes[2] = new Rect(box.x + w1 + w2, box.y, w3, h);
				nboxes[3] = new Rect(box.x + w1 + w2 + w3, box.y, w4, h);
				nboxes[4] = new Rect(box.x + w1 + w2 + w3 + w4, box.y, w5, h);
			} else {
				w = box.w;
				h1 = ratio1 * box.h;
				h2 = ratio2 * box.h;
				h3 = ratio3 * box.h;
				h4 = ratio4 * box.h;
				h5 = ratio5 * box.h;
				nboxes[0] = new Rect(box.x, box.y, w, h1);
				nboxes[1] = new Rect(box.x, box.y + h1, w, h2);
				nboxes[2] = new Rect(box.x, box.y + h1 + h2, w, h3);
				nboxes[3] = new Rect(box.x, box.y + h1 + h2 + h3, w, h4);
				nboxes[4] = new Rect(box.x, box.y + h1 + h2 + h3 + h4, w, h5);
			}
	
			origAvgAR = computeAverageAspectRatio(boxes);
			newAvgAR = computeAverageAspectRatio(nboxes);
			if (newAvgAR < origAvgAR) {
				boxes = nboxes;
			}
		}
	
		return boxes;
    }

	private function arraycopy(src:Array, srcPos:Number, dest:Array, destPos:Number, len:Number):Void{
		var tmp_array:Array = new Array();
		
		//collect
		for(var i = srcPos; i< srcPos+len; i++){
			tmp_array.push(src[i]);
		}
		
		//add
		var cnt:Number = 0;
		for(var i = destPos; i< destPos+len; i++){
			dest[i] = tmp_array[cnt];
			cnt++;
		}
	}
	
    private function computePivotIndex(sizes_array:Array):Number {
		var index:Number = 0;
		var leftSize:Number, rightSize:Number;
		var ratio:Number;
		var bestRatio:Number = 0;
		var biggest:Number;
		var isFirst:Boolean = true;
	
		switch (pivotType) {
		case PIVOT_BY_MIDDLE:
			index = (sizes_array.length - 1) / 2;
			break;
		case PIVOT_BY_SPLIT_SIZE:
			leftSize = 0;
			rightSize = computeSize(sizes_array);
	
			for (var i=0; i<sizes_array.length; i++) {
				ratio = Math.max((leftSize / rightSize), (rightSize / leftSize));
				if (isFirst || (ratio < bestRatio)) {
					isFirst = false;
					bestRatio = ratio;
					index = i;
				}
				leftSize += sizes_array[i];
				rightSize -= sizes_array[i];
			}
			break;
		case PIVOT_BY_BIGGEST:
			biggest = 0;
			for (var i=0; i<sizes_array.length; i++) {
				if (isFirst || (sizes_array[i] > biggest)) {
					isFirst = false;
					biggest = sizes_array[i];
					index = i;
				}
			}
			break;
		}
	
		return Math.round(index);
    }

    private function computeSize(sizes_array:Array):Number {
		var size:Number = 0;
		for (var i=0; i<sizes_array.length; i++) {
			size += sizes_array[i];
		}
		return size;
    }

    private function computeSize2(sizes:Array, i1:Number, i2:Number):Number {
		var size:Number = 0;
		for (var i=i1; i<=i2; i++) {
			size += sizes[i];
		}
		return size;
    }

    private function computeAverageAspectRatio(rects_array:Array):Number {
		var ar:Number;
		var tar:Number = 0;
		var w:Number, h:Number;
		var numRects:Number = 0;
	
		for (var i=0; i<rects_array.length; i++) {
			w = rects_array[i].w;
			h = rects_array[i].h;
			if ((w != 0) && (h != 0)) {
				ar = Math.max((w / h), (h / w));
				tar += ar;
				numRects++;
			}
		}
		tar /= numRects;
		return tar;
    }

}
